/*
 * @lc app=leetcode.cn id=316 lang=cpp
 *
 * [316] 去除重复字母
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    string removeDuplicateLetters(string s)
    {
        if (s.size() < 2)
            return s;

        vector<int> visted(26, 0), nums(26, 0);
        for (auto &c : s)
        {
            nums[c - 'a']++;
        }
        string res;

        for (auto &c : s)
        {
            if (!visted[c - 'a'])
            {
                while (res.size() && res.back() > c)
                {
                    if (nums[res.back() - 'a'])
                    {
                        visted[res.back() - 'a'] = false;
                        res.pop_back();
                    }
                    else break;
                }
                res.push_back(c);
                visted[c - 'a'] = true;
            }
            nums[c - 'a']--;
        }

        return res;
    }
};
// @lc code=end
